﻿//【进阶】38.哈希--海量数据处理（无代码）
//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using namespace std;
#include<string>
#include<vector>
#include<list>


//【命名空间】

//【类声明】

//【函数声明】
void Test1();void Test2();void Test3();


//【主函数】
int main()
{
	cout << "****主函数开始****" << endl;
	Test1();
	Test2();
	Test3();
	cout << "****主函数结束****" << endl;
	return 0;
}

//【函数定义】

/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;
	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;
	cout << "****测试用例结束****" << endl << endl;
}




//【笔记】
//【进阶】38.哈希--海量数据处理
	//海量数据处理经常用到的几种方式有：位图、布隆过滤器、哈希切分
	//位图：	
		//1.100亿个整数找出只出现一次的整数
			// a.利用一个位图，每两位表示一个数3中状态00不存在01存在且出现一次11存在且出现超1次
			// b.利用两个位图，一个表存在与否，另一个根据前者表是否超1次 
		//2.两个文件分别有100亿整数，只有1G内存，如果找交集
			// a.将其中一个文件整数放位图中，读另一个文件整数，判断在不在位图，在为交集，不在不为交集，消耗约500MB内存
			// b.将文件1整数映射到位图1中，文件2中整数映射到位图2中，两个位图按位与，消耗约1GB内存 
		//3.位图应用变形：1个文件有100亿int，1G内存，设计算法找到出现不超2次的整数
			// 两bit表示1个数00表示无、01表示1次、10表示2次、11表示2次以上，其他和第一题一致
	//布隆过滤器：
		//1.给两个文件，分别有100亿query，1G内存，如何找到两个文件交集给处精确和近似算法
			//分析：假设平均1个query30-60byte，100亿个占用300-600G
			// a.将文件1查询映射到布隆过滤器，读取文件2判断是否在布隆//缺陷是交集结果存在误判
			// b.将两个文件分别平均切分为1000份子文件，放在内存中利用set逐一比较
			// c.【哈希切分】，同样先将文件切分为1000个子文件，切分i=hashstr(query)%1000,i是多少就放在对应编号子文件
			// file_a[i]只需要和file_b[i]在set中比较即可 
		//2.如何拓展布隆过滤器使其支持删除
			//利用位表示计数器，选择合适的位数控制计数器计数上限，如1字节最多技术到256个数，假设有260个重复就会存在计数溢出
			// 2个字节会相对安全，可以计数到6万多次
	//【哈希切分】
		//在发生切分基数变化时所有哈希映射关系都需要修正和重置，而在实际工程中，如果数据体量很大时数据迁移代价过高
		//一致性哈希
			// 所以采用一致性哈希，即切分基数设置的足够大最大可为2^32（机器上记录的最大值）
			// 同时将一段范围的值去映射一个位置，当增加映射空间时，那不需要所有数据迁移，只需要迁移部分负载重的映射位置的数据 
	//
	//  


		









